#include "main/utils.h"
using namespace std;

int sum(const vector<int>& nums) {
  int ret = 0;
  for (auto ele : nums) {
    ret += ele;
  }
  return ret;
}

void combineSumCore(const vector<int>& nums,
                    const int& target,
                    int index,
                    vector<int>& result,
                    vector<vector<int>>& results) {
  if (sum(result) == target) {
    results.push_back(result);
    return;
  }
  if (sum(result) > target || index == nums.size()) {
    return;
  }
  combineSumCore(nums, target, index + 1, result, results);
  result.push_back(nums[index]);
  combineSumCore(nums, target, index, result, results);
  result.pop_back();
}

vector<vector<int>> combineSum(const vector<int>& nums, const int& sum) {
  vector<vector<int>> results;
  vector<int> result;
  combineSumCore(nums, sum, 0, result, results);
  return results;
}

int main() {
  vector<int> nums = {2, 3, 5};
  int sum = 8;
  auto ret = combineSum(nums, sum);
  printVec("o81", ret);

  return 0;
}
